// xutility internal header -*-c++-*-
// Copyright 2003-2010 IAR Systems AB. 
#ifndef _XUTILITY_
#define _XUTILITY_

#ifndef _SYSTEM_BUILD
#pragma system_include
#endif

#include <climits>
#include <utility>
#include <iutility>
#include <istream>
_STD_BEGIN

#define _DEBUG_ERROR(mesg)
#define _DEBUG_LT(x, y)	((x) < (y))
#define _DEBUG_LT_PRED(pred, x, y)	pred(x, y)

//      ITERATOR STUFF (from <iterator>)

                // ITERATOR TAGS
struct input_iterator_tag
{};     // identifying tag for input iterators

struct output_iterator_tag
{};     // identifying tag for output iterators

struct forward_iterator_tag
  : public input_iterator_tag
{};     // identifying tag for forward iterators

struct bidirectional_iterator_tag
  : public forward_iterator_tag
{};     // identifying tag for bidirectional iterators

struct random_access_iterator_tag
  : public bidirectional_iterator_tag
{};     // identifying tag for random-access iterators

                // TEMPLATE CLASS iterator
template<class _Category,
         class _Ty,
         class _Diff = ptrdiff_t,
         class _Pointer = _Ty *,
         class _Reference = _Ty&>
struct iterator
{       // base type for all iterator classes
  typedef _Category iterator_category;
  typedef _Ty value_type;
  typedef _Diff difference_type;
  typedef _Diff distance_type;    // retained
  typedef _Pointer pointer;
  typedef _Reference reference;
};

template<class _Ty,
         class _Diff,
         class _Pointer,
         class _Reference>
struct _Bidit
  : public iterator<bidirectional_iterator_tag, _Ty, _Diff,
  _Pointer, _Reference>
{};     // base for bidirectional iterators

template<class _Ty,
         class _Diff,
         class _Pointer,
         class _Reference>
struct _Ranit
  : public iterator<random_access_iterator_tag, _Ty, _Diff,
  _Pointer, _Reference>
{};     // base for random-access iterators

struct _Outit
  : public iterator<output_iterator_tag, void, void,
  void, void>
{};     // base for output iterators

// Helper classes for iterator_traits
template<bool _HasCategory, typename _Iter>
struct _IteratorTraitsBase
{
  // _Iter has not iterator_category member. Don't define any typedefs here.
};
template<typename _Iter>
struct _IteratorTraitsBase<true, _Iter>
{
  // _Iter has an iterator_category member. Define relevant typedefs.
  typedef typename _Iter::iterator_category iterator_category;
  typedef typename _Iter::value_type value_type;
  typedef typename _Iter::difference_type difference_type;
  typedef difference_type distance_type;  // retained
  typedef typename _Iter::pointer pointer;
  typedef typename _Iter::reference reference;
};

template<typename _Ty>
struct _HasIteratorCategoryMember
{
  typedef char _No;
  struct _Yes { char _A[17]; };
  static _No _Test(...);
  template<typename _Ty2>
  static
  typename _TypeUtil::_Select<true,
                              _Yes,
                              typename _Ty2::iterator_category>::_Type
  _Test(_Ty2 const &);
  static _Ty _Make();
  enum { _Result = sizeof(_Test(_Make())) == sizeof(_Yes) };
};

                // TEMPLATE CLASS iterator_traits
// Inherit from _IteratorTraitsBase so that we can use the existence
// of iterator_traits<X>::iterator_category as a test of whether X is
// an iterator.
template<class _Iter>
struct iterator_traits
  : _IteratorTraitsBase<_HasIteratorCategoryMember<_Iter>::_Result, _Iter>
{       // get traits from iterator _Iter
};

template<class _Ty>
struct iterator_traits<_Ty *>
{       // get traits from pointer
  typedef random_access_iterator_tag iterator_category;
  typedef _Ty value_type;
  typedef typename _TypeUtil::_PointerInfo<_Ty *>::_IndexType difference_type;
  typedef difference_type distance_type;        // retained
  typedef _Ty *pointer;
  typedef _Ty& reference;
};

template<class _Ty>
struct iterator_traits<const _Ty *>
{       // get traits from const pointer
  typedef random_access_iterator_tag iterator_category;
  typedef _Ty value_type;
  typedef typename iterator_traits<_Ty *>::difference_type difference_type;
  typedef difference_type distance_type;        // retained
  typedef const _Ty *pointer;
  typedef const _Ty& reference;
};

// TEMPLATE FUNCTION _Iter_cat
template<class _Iter> inline
typename iterator_traits<_Iter>::iterator_category
_Iter_cat(const _Iter&)
{       // return category from iterator argument
  typename iterator_traits<_Iter>::iterator_category _Cat;
  return (_Cat); 
}

// Helper class to handle the distance function.
template<typename _Cat> struct _DistanceHelper
{
#pragma basic_template_matching
  template<typename _InIt> inline static
  typename iterator_traits<_InIt>::difference_type
  _Distance(_InIt _First, _InIt _Last)
  {
    typename iterator_traits<_InIt>::difference_type _Off = 0;
    for (; _First != _Last; ++_First)
      ++_Off;
    return _Off;
  }
};

template<> struct _DistanceHelper<random_access_iterator_tag>
{
#pragma basic_template_matching
  template<typename _InIt> inline static
  typename iterator_traits<_InIt>::difference_type
  _Distance(_InIt _First, _InIt _Last)
  {
    return _Last - _First;
  }
};

// TEMPLATE FUNCTIONS distance and _Distance
#pragma basic_template_matching
template<class _InIt> inline
typename iterator_traits<_InIt>::difference_type
distance(_InIt _First, _InIt _Last)
{       // return distance between iterators
  typedef typename iterator_traits<_InIt>::iterator_category _Cat;
  return _DistanceHelper<_Cat>::_Distance(_First, _Last);
}

// TEMPLATE CLASS _Ptrit
template<class _Ty,
         class _Diff,
         class _Pointer,
         class _Reference,
         class _Pointer2,
         class _Reference2>
class _Ptrit
  : public _Ranit<_Ty, _Diff, _Pointer, _Reference>
{       // wrap pointer as random-access iterator
public:
  typedef _Ptrit<_Ty, _Diff, _Pointer, _Reference,
          _Pointer2, _Reference2> _Myt;
  _Ptrit()
  {}      // construct with uninitialized wrapped pointer

  _Ptrit(_Pointer _Ptr)
    : current(_Ptr)
  {}      // construct wrapped pointer from _Ptr

  _Ptrit(const _Ptrit<_Ty, _Diff, _Pointer2, _Reference2,
         _Pointer2, _Reference2>& _Iter)
    : current(_Iter.base())
  {}      // const converter or copy constructor

  _Pointer base() const
  {       // return wrapped pointer
    return (current); 
  }

  _Reference operator*() const
  {       // return designated value
    return (*current); 
  }

  _Pointer operator->() const
  {       // return pointer to class object
    return (&**this); 
  }

  _Myt& operator++()
  {       // preincrement
    ++current;
    return (*this); 
  }

  _Myt operator++(int)
  {       // postincrement
    _Myt _Tmp = *this;
    ++current;
    return (_Tmp); 
  }

  _Myt& operator--()
  {       // predecrement
    --current;
    return (*this); 
  }

  _Myt operator--(int)
  {       // postdecrement
    _Myt _Tmp = *this;
    --current;
    return (_Tmp); 
  }

        bool operator==(int _Right) const
  {       // test if wrapped pointer == integer (null pointer constant)
    return (current == (_Pointer)_Right); 
  }

  bool operator==(const _Myt& _Right) const
  {       // test for iterator equality
    return (current == _Right.current); 
  }

  bool operator!=(const _Myt& _Right) const
  {       // test for iterator inequality
    return (!(*this == _Right)); 
  }

  _Myt& operator+=(_Diff _Off)
  {       // increment by integer
    current += _Off;
    return (*this); 
  }

  _Myt operator+(_Diff _Off) const
  {       // return this + integer
    return (_Myt(current + _Off)); 
  }

  _Myt& operator-=(_Diff _Off)
  {       // decrement by integer
    current -= _Off;
    return (*this); 
  }

  _Myt operator-(_Diff _Off) const
  {       // return this - integer
    return (_Myt(current - _Off)); 
  }

  _Reference operator[](_Diff _Off) const
  {       // subscript
    return (*(*this + _Off)); 
  }

        bool operator<(const _Myt& _Right) const
  {       // test if this < _Right
    return (current < _Right.current); 
  }

  bool operator>(const _Myt& _Right) const
  {       // test if this > _Right
    return (_Right < *this); 
  }

  bool operator<=(const _Myt& _Right) const
  {       // test if this <= _Right
    return (!(_Right < *this)); 
  }

  bool operator>=(const _Myt& _Right) const
  {       // test if this >= _Right
    return (!(*this < _Right)); 
  }

  _Diff operator-(const _Myt& _Right) const
  {       // return difference of iterators
    return (current - _Right.current); 
  }

protected:
  _Pointer current;       // the wrapped pointer
};

// _Ptrit TEMPLATE FUNCTIONS
template<class _Ty,
         class _Diff,
         class _Pointer,
         class _Reference,
         class _Pointer2,
         class _Reference2> inline
_Ptrit<_Ty, _Diff, _Pointer, _Reference, _Pointer2, _Reference2>
operator+(_Diff _Off,
          const _Ptrit<_Ty, _Diff, _Pointer, _Reference,
          _Pointer2, _Reference2>& _Right)
{       // return iterator + integer
  return (_Right + _Off); 
}

template<class _Ty,
         class _Diff,
         class _Pointer,
         class _Reference,
         class _Pointer2,
         class _Reference2> inline
bool operator==(
                const _Ptrit<_Ty, _Diff, _Pointer2, _Reference2,
  _Pointer2, _Reference2>& _Left,
  const _Ptrit<_Ty, _Diff, _Pointer, _Reference,
  _Pointer2, _Reference2>& _Right)
        {       // test for _Ptrit<non-const *> == _Ptrit<const *>
        return (_Right == _Left); }

template<class _Ty,
  class _Diff,
  class _Pointer,
  class _Reference,
  class _Pointer2,
  class _Reference2> inline
bool operator!=(
                const _Ptrit<_Ty, _Diff, _Pointer2, _Reference2,
  _Pointer2, _Reference2>& _Left,
  const _Ptrit<_Ty, _Diff, _Pointer, _Reference,
  _Pointer2, _Reference2>& _Right)
{       // test for _Ptrit inequality
        return (_Right != _Left); }

template<class _Ty,
  class _Diff,
  class _Pointer,
  class _Reference,
  class _Pointer2,
  class _Reference2> inline
bool operator<(
                const _Ptrit<_Ty, _Diff, _Pointer2, _Reference2,
  _Pointer2, _Reference2>& _Left,
  const _Ptrit<_Ty, _Diff, _Pointer, _Reference,
  _Pointer2, _Reference2>& _Right)
        {       // test for _Ptrit<non-const *> < _Ptrit<const *>
        return (_Right > _Left); }

template<class _Ty,
  class _Diff,
  class _Pointer,
  class _Reference,
  class _Pointer2,
  class _Reference2> inline
bool operator>(
                const _Ptrit<_Ty, _Diff, _Pointer2, _Reference2,
  _Pointer2, _Reference2>& _Left,
  const _Ptrit<_Ty, _Diff, _Pointer, _Reference,
  _Pointer2, _Reference2>& _Right)
        {       // test for _Ptrit<non-const *> > _Ptrit<const *>
        return (_Right < _Left); }

template<class _Ty,
  class _Diff,
  class _Pointer,
  class _Reference,
  class _Pointer2,
  class _Reference2> inline
bool operator<=(
                const _Ptrit<_Ty, _Diff, _Pointer2, _Reference2,
  _Pointer2, _Reference2>& _Left,
  const _Ptrit<_Ty, _Diff, _Pointer, _Reference,
  _Pointer2, _Reference2>& _Right)
        {       // test for _Ptrit<non-const *> <= _Ptrit<const *>
        return (_Right >= _Left); }

template<class _Ty,
  class _Diff,
  class _Pointer,
  class _Reference,
  class _Pointer2,
  class _Reference2> inline
bool operator>=(
                const _Ptrit<_Ty, _Diff, _Pointer2, _Reference2,
  _Pointer2, _Reference2>& _Left,
  const _Ptrit<_Ty, _Diff, _Pointer, _Reference,
  _Pointer2, _Reference2>& _Right)
        {       // test for _Ptrit<non-const *> >= _Ptrit<const *>
        return (_Right <= _Left); }

// TEMPLATE CLASS reverse_iterator
template<class _RanIt>
class reverse_iterator
{       // wrap iterator to run it backwards
public:
  typedef reverse_iterator<_RanIt> _Myt;
  typedef typename iterator_traits<_RanIt>::difference_type difference_type;
  typedef typename iterator_traits<_RanIt>::pointer pointer;
  typedef typename iterator_traits<_RanIt>::reference reference;
  typedef _RanIt iterator_type;

  // Don't inherit from iterator<_RanIt> to get these typedefs.
  // If we instantiate this class with an iterator that does inherit from
  // iterator<_RanIt> the empty base class optimization is blocked.
  typedef typename iterator_traits<_RanIt>::iterator_category
                                                            iterator_category;
  typedef typename iterator_traits<_RanIt>::value_type value_type;
  typedef difference_type distance_type;    // retained

  reverse_iterator()
  {}      // construct with default wrapped iterator

  explicit reverse_iterator(_RanIt _Right)
    : current(_Right)
  {}      // construct wrapped iterator from _Right

  template<class _Other>
  reverse_iterator(const reverse_iterator<_Other>& _Right)
    : current(_Right.base())
  {}      // initialize with compatible base

  _RanIt base() const
  {       // return wrapped iterator
    return (current); 
  }

  reference operator*() const
  {       // return designated value
    _RanIt _Tmp = current;
    return (*--_Tmp); 
  }

  pointer operator->() const
  {       // return pointer to class object
    return (&**this); 
  }

  _Myt& operator++()
  {       // preincrement
    --current;
    return (*this); 
  }

  _Myt operator++(int)
  {       // postincrement
    _Myt _Tmp = *this;
    --current;
    return (_Tmp); 
  }

  _Myt& operator--()
  {       // predecrement
    ++current;
    return (*this); 
  }

  _Myt operator--(int)
  {       // postdecrement
    _Myt _Tmp = *this;
    ++current;
    return (_Tmp); 
  }

  bool _Equal(const _Myt& _Right) const
  {       // test for iterator equality
    return (current == _Right.current); 
  }

// N.B. functions valid for random-access iterators only beyond this point

  _Myt& operator+=(difference_type _Off)
  {       // increment by integer
    current -= _Off;
    return (*this); 
  }

  _Myt operator+(difference_type _Off) const
  {       // return this + integer
    return (_Myt(current - _Off)); 
  }

  _Myt& operator-=(difference_type _Off)
  {       // decrement by integer
    current += _Off;
    return (*this); 
  }

  _Myt operator-(difference_type _Off) const
  {       // return this - integer
    return (_Myt(current + _Off)); 
  }

  reference operator[](difference_type _Off) const
  {       // subscript
    return (*(*this + _Off)); 
  }

  bool _Less(const _Myt& _Right) const
  {       // test if this < _Right
    return (_Right.current < current);
  }

  difference_type _Minus(const _Myt& _Right) const
  {       // return difference of iterators
    return (_Right.current - current); 
  }

protected:
  _RanIt current; // the wrapped iterator
};

// reverse_iterator TEMPLATE OPERATORS
template<class _RanIt,
  class _Diff> inline
reverse_iterator<_RanIt> operator+(_Diff _Off,
                                   const reverse_iterator<_RanIt>& _Right)
{       // return reverse_iterator + integer
  return (_Right + _Off); 
}

template<class _RanIt> inline
typename reverse_iterator<_RanIt>::difference_type
operator-(const reverse_iterator<_RanIt>& _Left,
          const reverse_iterator<_RanIt>& _Right)
{       // return difference of reverse_iterators
  return (_Left._Minus(_Right)); 
}

template<class _RanIt> inline
bool operator==(const reverse_iterator<_RanIt>& _Left,
                const reverse_iterator<_RanIt>& _Right)
{       // test for reverse_iterator equality
  return (_Left._Equal(_Right)); 
}

template<class _RanIt> inline
bool operator!=(const reverse_iterator<_RanIt>& _Left,
                const reverse_iterator<_RanIt>& _Right)
{       // test for reverse_iterator inequality
  return (!(_Left == _Right)); 
}

template<class _RanIt> inline
bool operator<(const reverse_iterator<_RanIt>& _Left,
               const reverse_iterator<_RanIt>& _Right)
{       // test for reverse_iterator < reverse_iterator
  return (_Left._Less(_Right)); 
}

template<class _RanIt> inline
bool operator>(const reverse_iterator<_RanIt>& _Left,
               const reverse_iterator<_RanIt>& _Right)
{       // test for reverse_iterator > reverse_iterator
  return (_Right < _Left); 
}

template<class _RanIt> inline
bool operator<=(const reverse_iterator<_RanIt>& _Left,
                const reverse_iterator<_RanIt>& _Right)
{       // test for reverse_iterator <= reverse_iterator
  return (!(_Right < _Left)); 
}

template<class _RanIt> inline
bool operator>=(const reverse_iterator<_RanIt>& _Left,
                const reverse_iterator<_RanIt>& _Right)
{       // test for reverse_iterator >= reverse_iterator
  return (!(_Left < _Right)); 
}

// TEMPLATE CLASS reverse_bidirectional_iterator (retained)
template<class _BidIt,
  class _Ty,
  class _Reference = _Ty&,
  class _Pointer = _Ty *,
  class _Diff = ptrdiff_t>
class reverse_bidirectional_iterator
  : public _Bidit<_Ty, _Diff, _Pointer, _Reference>
{       // wrap bidirectional iterator to run it backwards
public:
  typedef reverse_bidirectional_iterator<_BidIt, _Ty, _Reference,
          _Pointer, _Diff> _Myt;
  typedef _BidIt iterator_type;

  reverse_bidirectional_iterator()
  {}      // construct with default wrapped iterator

  explicit reverse_bidirectional_iterator(_BidIt _Right)
    : current(_Right)
  {}      // construct wrapped iterator from _Right

  _BidIt base() const
  {       // return wrapped iterator
    return (current); 
  }

  _Reference operator*() const
  {       // return designated value
    _BidIt _Tmp = current;
    return (*--_Tmp); 
  }

  _Pointer operator->() const
  {       // return pointer to class object
    _Reference _Tmp = **this;
    return (&_Tmp); 
  }

  _Myt& operator++()
  {       // preincrement
    --current;
    return (*this); 
  }

  _Myt operator++(int)
  {       // postincrement
    _Myt _Tmp = *this;
    --current;
    return (_Tmp); 
  }

  _Myt& operator--()
  {       // predecrement
    ++current;
    return (*this); 
  }

  _Myt operator--(int)
  {       // postdecrement
    _Myt _Tmp = *this;
    ++current;
    return (_Tmp); 
  }

  bool operator==(const _Myt& _Right) const
  {       // test for iterator equality
    return (current == _Right.current); 
  }

  bool operator!=(const _Myt& _Right) const
  {       // test for iterator inequality
    return (!(*this == _Right)); 
  }

protected:
  _BidIt current; // the wrapped iterator
};

// TEMPLATE CLASS _Revbidit
template<class _BidIt,
  class _BidIt2 = _BidIt>
class _Revbidit
  : public iterator<
typename iterator_traits<_BidIt>::iterator_category,
                             typename iterator_traits<_BidIt>::value_type,
                             typename iterator_traits<_BidIt>::difference_type,
                             typename iterator_traits<_BidIt>::pointer,
                             typename iterator_traits<_BidIt>::reference>
{       // wrap bidirectional iterator to run it backwards
public:
  typedef _Revbidit<_BidIt, _BidIt2> _Myt;
  typedef typename iterator_traits<_BidIt>::difference_type _Diff;
  typedef typename iterator_traits<_BidIt>::pointer _Pointer;
  typedef typename iterator_traits<_BidIt>::reference _Reference;
  typedef _BidIt iterator_type;

  _Revbidit()
  {}      // construct with default wrapped iterator

  explicit _Revbidit(_BidIt _Right)
    : current(_Right)
  {}      // construct wrapped iterator from _Right

  _Revbidit(const _Revbidit<_BidIt2>& _Other)
    : current (_Other.base())
  {}      // const converter or copy constructor

  _BidIt base() const
  {       // return wrapped iterator
    return (current); 
  }

  _Reference operator*() const
  {       // return designated value
    _BidIt _Tmp = current;
    return (*--_Tmp); 
  }

  _Pointer operator->() const
  {       // return pointer to class object
    _Reference _Tmp = **this;
    return (&_Tmp); 
  }

  _Myt& operator++()
  {       // preincrement
    --current;
    return (*this); 
  }

  _Myt operator++(int)
  {       // postincrement
    _Myt _Tmp = *this;
    --current;
    return (_Tmp); 
  }

  _Myt& operator--()
  {       // predecrement
    ++current;
    return (*this); 
  }

  _Myt operator--(int)
  {       // postdecrement
    _Myt _Tmp = *this;
    ++current;
    return (_Tmp); 
  }

  bool operator==(const _Myt& _Right) const
  {       // test for iterator equality
    return (current == _Right.current); 
  }

  bool operator!=(const _Myt& _Right) const
  {       // test for iterator inequality
    return (!(*this == _Right)); 
  }

protected:
  _BidIt current;
};

// TEMPLATE CLASS istreambuf_iterator
template<class _Elem,
  class _Traits = char_traits>
class istreambuf_iterator
  : public iterator<input_iterator_tag,
  _Elem, typename _Traits::off_type, _Elem *, _Elem&>
{       // wrap stream buffer as input iterator
public:
  typedef istreambuf_iterator<_Elem, _Traits> _Myt;
  typedef char char_type;
  typedef char_traits traits_type;
  typedef streambuf streambuf_type;
  typedef istream istream_type;
  typedef typename traits_type::int_type int_type;

  istreambuf_iterator(streambuf_type *_Sb = 0) _THROW0()
    : _Strbuf(_Sb), _Got(_Sb == 0)
  {}      // construct from stream buffer _Sb

  istreambuf_iterator(istream_type& _Istr) _THROW0()
    : _Strbuf(_Istr.rdbuf()), _Got(_Istr.rdbuf() == 0)
  {}      // construct from stream buffer in istream _Istr

  _Elem operator*() const
  {       // return designated value
    if (!_Got)
      ((_Myt *)this)->_Peek();
    return (_Val); 
  }

  _Myt& operator++()
  {       // preincrement
    _Inc();
    return (*this); 
  }

  _Myt operator++(int)
  {       // postincrement
    if (!_Got)
      _Peek();
    _Myt _Tmp = *this;
    _Inc();
    return (_Tmp); 
  }

  bool equal(const _Myt& _Right) const
  {       // test for equality
    if (!_Got)
      ((_Myt *)this)->_Peek();
    if (!_Right._Got)
      ((_Myt *)&_Right)->_Peek();
    return (_Strbuf == 0 && _Right._Strbuf == 0
            || _Strbuf != 0 && _Right._Strbuf != 0); 
  }

private:
  void _Inc()
  {       // skip to next input element
    if (_Strbuf == 0
        || traits_type::eq_int_type(traits_type::eof(),
                                    _Strbuf->sbumpc()))
      _Strbuf = 0, _Got = true;
    else
      _Got = false; 
  }

  _Elem _Peek()
  {       // peek at next input element
    int_type _Meta;
    if (_Strbuf == 0
        || traits_type::eq_int_type(traits_type::eof(),
                                    _Meta = _Strbuf->sgetc()))
      _Strbuf = 0;
    else
      _Val = traits_type::to_char_type(_Meta);
    _Got = true;
    return (_Val); 
  }

  streambuf_type *_Strbuf;        // the wrapped stream buffer
  bool _Got;      // true if _Val is valid
  _Elem _Val;     // next element to deliver
};

// istreambuf_iterator TEMPLATE OPERATORS
template<class _Elem,
  class _Traits> inline
bool operator==(
  const istreambuf_iterator<_Elem, _Traits>& _Left,
  const istreambuf_iterator<_Elem, _Traits>& _Right)
{       // test for istreambuf_iterator equality
  return (_Left.equal(_Right)); 
}

template<class _Elem,
  class _Traits> inline
bool operator!=(
  const istreambuf_iterator<_Elem, _Traits>& _Left,
  const istreambuf_iterator<_Elem, _Traits>& _Right)
{       // test for istreambuf_iterator inequality
  return (!(_Left == _Right)); 
}

// TEMPLATE CLASS ostreambuf_iterator
template<class _Elem,
  class _Traits>
class ostreambuf_iterator
  : public _Outit
{       // wrap stream buffer as output iterator
  typedef ostreambuf_iterator<_Elem, _Traits> _Myt;
public:
  typedef char char_type;
  typedef char_traits traits_type;
  typedef streambuf streambuf_type;
  typedef ostream ostream_type;

  ostreambuf_iterator(streambuf_type *_Sb) _THROW0()
    : _Failed(false), _Strbuf(_Sb)
  {}      // construct from stream buffer _Sb

  ostreambuf_iterator(ostream_type& _Ostr) _THROW0()
    : _Failed(false), _Strbuf(_Ostr.rdbuf())
  {}      // construct from stream buffer in _Ostr

  _Myt& operator=(_Elem _Right)
  {       // store element and increment
    if (_Strbuf == 0
        || traits_type::eq_int_type(_Traits::eof(),
                                    _Strbuf->sputc(_Right)))
      _Failed = true;
    return (*this); 
  }

  _Myt& operator*()
  {       // pretend to get designated element
    return (*this); 
  }

  _Myt& operator++()
  {       // pretend to preincrement
    return (*this); 
  }

  _Myt& operator++(int)
  {       // pretend to postincrement
    return (*this); 
  }

  bool failed() const _THROW0()
  {       // return true if any stores failed
    return (_Failed); 
  }

private:
  bool _Failed;   // true if any stores have failed
  streambuf_type *_Strbuf;        // the wrapped stream buffer
};

//      ALGORITHM STUFF (from <algorithm>)

                // TEMPLATE FUNCTION copy
#pragma basic_template_matching
template<class _InIt,
  class _OutIt> inline
_OutIt _Copy_opt0(_InIt _First, _InIt _Last, _OutIt _Dest)
{       // copy [_First, _Last) to [_Dest, ...), arbitrary iterators
  for (; _First != _Last; ++_Dest, ++_First)
    *_Dest = *_First;
  return (_Dest); 
}

// Default copy, not using library call
template<typename _Ty, bool _UseLibCall>
struct _Copier
{
  static _Ty * _Copy(_Ty const * _First, _Ty const * _Last, _Ty * _Dest)
  {
    return _Copy_opt0(_First, _Last, _Dest);
  }
};

// Use a library routine to copy
template<typename _Ty>
struct _Copier<_Ty, true>
{
  static _Ty * _Copy(_Ty const * _First, _Ty const * _Last, _Ty * _Dest)
  {
    if      (__ALIGNOF__(_Ty) == 2)
      return (_Ty *) __iar_Copy_a2(_First, _Last, _Dest);
    else if (__ALIGNOF__(_Ty) == 4)
      return (_Ty *) __iar_Copy_a4(_First, _Last, _Dest);
    else if (__ALIGNOF__(_Ty) == 8)
      return (_Ty *) __iar_Copy_a8(_First, _Last, _Dest);
    else
    {
      typename _TypeUtil::_PointerInfo<_Ty *>::_IndexType _Off = _Last - _First;      // NB: non-overlapping move
      return ((_Ty *)_CSTD memmove(&*_Dest, &*_First,
                                _Off * sizeof (*_First)) + _Off); 
    }
  }
};

#pragma basic_template_matching
template<class _InIt,
  class _OutIt> inline
_OutIt _Copy_opt(_InIt _First, _InIt _Last, _OutIt _Dest)
{       // copy [_First, _Last) to [_Dest, ...), arbitrary iterators
  return _Copy_opt0(_First, _Last, _Dest);
}

#pragma basic_template_matching
template<class _Ty>
inline
_Ty * _Copy_opt(_Ty const * _First, _Ty const * _Last, _Ty * _Dest)
{       // copy [_First, _Last) to [_Dest, ...), pointers to scalars
  // Use a library routine to copy if bitwise is okay, and we're using
  // default pointers.
  typedef _Copier<_Ty,
                     __assignment_by_bitwise_copy_allowed(*_First)
                  && _TypeUtil::_IsDefaultPointer<_Ty *>::_Result>
          _TheCopier;
  return _TheCopier::_Copy(_First, _Last, _Dest);
}

#pragma basic_template_matching
template<class _Ty1>
inline
_Ty1 *_Copy_opt(_Ty1 *_First, _Ty1 *_Last, _Ty1 *_Dest)
{
  return _Copy_opt(const_cast<_Ty1 const *>(_First),
                   const_cast<_Ty1 const *>(_Last),
                   _Dest);
}

#pragma basic_template_matching
template<class _InIt,
  class _OutIt> inline
_OutIt copy(_InIt _First, _InIt _Last, _OutIt _Dest)
{       // copy [_First, _Last) to [_Dest, ...)
  return _Copy_opt(_First, _Last, _Dest);
}

// TEMPLATE FUNCTION copy_backward
#pragma basic_template_matching
template<class _BidIt1,
  class _BidIt2> inline
_BidIt2 _Copy_backward_opt0(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
{       // copy [_First, _Last) backwards to [..., _Dest), arbitrary iterators
  while (_First != _Last)
    *--_Dest = *--_Last;
  return (_Dest); 
}

// Default copy, not using library call
template<typename _Ty, bool _UseLibCall>
struct _Backward_copier
{
  static _Ty * _Copy(_Ty const * _First, _Ty const * _Last, _Ty * _Dest)
  {
    return _Copy_backward_opt0(_First, _Last, _Dest);
  }
};

// Use a library routine to copy
template<typename _Ty>
struct _Backward_copier<_Ty, true>
{
  static _Ty * _Copy(_Ty const * _First, _Ty const * _Last, _Ty * _Dest)
  {
    if      (__ALIGNOF__(_Ty) == 2)
      return (_Ty *) __iar_Copy_backward_a2(_First, _Last, _Dest);
    else if (__ALIGNOF__(_Ty) == 4)
      return (_Ty *) __iar_Copy_backward_a4(_First, _Last, _Dest);
    else if (__ALIGNOF__(_Ty) == 8)
      return (_Ty *) __iar_Copy_backward_a8(_First, _Last, _Dest);
    else
    {
      typename _TypeUtil::_PointerInfo<_Ty *>::_IndexType _Off = _Last - _First; // NB: non-overlapping move
      return ((_Ty *)_CSTD memmove(&*_Dest - _Off, &*_First,
                                   _Off * sizeof (*_First))); 
    }
  }
};

#pragma basic_template_matching
template<class _BidIt1,
  class _BidIt2> inline
_BidIt2 _Copy_backward_opt(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
{       // copy [_First, _Last) backwards to [..., _Dest), arbitrary iterators
  return _Copy_backward_opt0(_First, _Last, _Dest);
}

#pragma basic_template_matching
template<class _Ty>
inline
_Ty * _Copy_backward_opt(_Ty const * _First, _Ty const * _Last, _Ty * _Dest)
{       // copy [_First, _Last) backwards to [..., _Dest), pointers to scalars
  // Use a library routine to copy if bitwise is okay, and we're using
  // default pointers.
  typedef _Backward_copier<_Ty,
                              __assignment_by_bitwise_copy_allowed(*_First)
                           && _TypeUtil::_IsDefaultPointer<_Ty *>::_Result>
          _TheCopier;
  return _TheCopier::_Copy(_First, _Last, _Dest);
}

// This override is needed in order to be a better match than the
// general case when the pointers are not pointers to const.
#pragma basic_template_matching
template<class _Ty1>
inline
_Ty1 *_Copy_backward_opt(_Ty1 *_First, _Ty1 *_Last, _Ty1 *_Dest)
{
  return _Copy_backward_opt(const_cast<_Ty1 const *>(_First),
                            const_cast<_Ty1 const *>(_Last),
                            _Dest);
}

#pragma basic_template_matching
template<class _BidIt1,
  class _BidIt2> inline
_BidIt2 copy_backward(_BidIt1 _First, _BidIt1 _Last, _BidIt2 _Dest)
{       // copy [_First, _Last) backwards to [..., _Dest)
  return _Copy_backward_opt(_First, _Last, _Dest);
}

// TEMPLATE FUNCTION mismatch
template<class _InIt1,
  class _InIt2> inline
pair<_InIt1, _InIt2>
mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
{       // return [_First1, _Last1) and [_First2, _Last2) mismatch
  for (; _First1 != _Last1 && *_First1 == *_First2; )
    ++_First1, ++_First2;
  return (pair<_InIt1, _InIt2>(_First1, _First2)); 
}

// TEMPLATE FUNCTION mismatch WITH PRED
template<class _InIt1,
  class _InIt2,
  class _Pr> inline
pair<_InIt1, _InIt2>
mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
{       // return [_First1, _Last1) and [_First2, _Last2) mismatch using _Pred
  for (; _First1 != _Last1 && _Pred(*_First1, *_First2); )
    ++_First1, ++_First2;
  return (pair<_InIt1, _InIt2>(_First1, _First2)); 
}

// TEMPLATE FUNCTION equal
template<class _InIt1,
  class _InIt2> inline
bool equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2)
{       // compare [_First1, _Last1) to [First2, ...)
  return (mismatch(_First1, _Last1, _First2).first == _Last1); 
}

inline bool equal(const char *_First1,
                  const char *_Last1, const char *_First2)
{       // compare [_First1, _Last1) to [First2, ...), for chars
  return (_CSTD memcmp(_First1, _First2, _Last1 - _First1) == 0); 
}

inline bool equal(const signed char *_First1,
                  const signed char *_Last1, const signed char *_First2)
{       // compare [_First1, _Last1) to [First2, ...), for signed chars
  return (_CSTD memcmp(_First1, _First2, _Last1 - _First1) == 0); 
}

inline bool equal(const unsigned char *_First1,
                  const unsigned char *_Last1, const unsigned char *_First2)
{       // compare [_First1, _Last1) to [First2, ...), for unsigned chars
  return (_CSTD memcmp(_First1, _First2, _Last1 - _First1) == 0); 
}

// TEMPLATE FUNCTION equal WITH PRED
template<class _InIt1,
  class _InIt2,
  class _Pr> inline
bool equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _Pr _Pred)
{       // compare [_First1, _Last1) to [First2, ...) using _Pred
  return (mismatch(_First1, _Last1, _First2, _Pred).first == _Last1); 
}

// TEMPLATE FUNCTION fill
template<class _FwdIt,
  class _Ty> inline
void fill(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
{       // copy _Val through [_First, _Last)
  for (; _First != _Last; ++_First)
    *_First = _Val; 
}

inline void fill(char *_First, char *_Last, int _Val)
{       // copy char _Val through [_First, _Last)
  _CSTD memset(_First, _Val, _Last - _First); 
}

inline void fill(signed char *_First, signed char *_Last, int _Val)
{       // copy signed char _Val through [_First, _Last)
  _CSTD memset(_First, _Val, _Last - _First); 
}

inline void fill(unsigned char *_First, unsigned char *_Last, int _Val)
{       // copy unsigned char _Val through [_First, _Last)
  _CSTD memset(_First, _Val, _Last - _First); 
}

// TEMPLATE FUNCTION fill_n
template<class _OutIt,
  class _Diff,
  class _Ty> inline
void fill_n(_OutIt _First, _Diff _Count, const _Ty& _Val)
{       // copy _Val _Count times through [_First, ...)
  for (; 0 < _Count; --_Count, ++_First)
    *_First = _Val; 
}

inline void fill_n(char *_First, size_t _Count, int _Val)
{       // copy char _Val _Count times through [_First, ...)
  _CSTD memset(_First, _Val, _Count); 
}

inline void fill_n(signed char *_First, size_t _Count, int _Val)
{       // copy signed char _Val _Count times through [_First, ...)
  _CSTD memset(_First, _Val, _Count); 
}

inline void fill_n(unsigned char *_First, size_t _Count, int _Val)
{       // copy unsigned char _Val _Count times through [_First, ...)
  _CSTD memset(_First, _Val, _Count); 
}

// TEMPLATE FUNCTION lexicographical_compare
template<class _InIt1,
  class _InIt2> inline
bool lexicographical_compare(_InIt1 _First1, _InIt1 _Last1,
                             _InIt2 _First2, _InIt2 _Last2)
{       // order [_First1, _Last1) vs. [First2, Last2)
  for (; _First1 != _Last1 && _First2 != _Last2; ++_First1, ++_First2)
    if (*_First1 < *_First2)
      return (true);
    else if (*_First2 < *_First1)
      return (false);
  return (_First1 == _Last1 && _First2 != _Last2); 
}

inline bool lexicographical_compare(
  const unsigned char *_First1, const unsigned char *_Last1,
  const unsigned char *_First2, const unsigned char *_Last2)
{       // order [_First1, _Last1) vs. [First2, Last2), for unsigned char
  ptrdiff_t _Num1 = _Last1 - _First1;
  ptrdiff_t _Num2 = _Last2 - _First2;
  int _Ans = _CSTD memcmp(_First1, _First2, _Num1 < _Num2 ? _Num1 : _Num2);
  return (_Ans < 0 || _Ans == 0 && _Num1 < _Num2); 
}

#if CHAR_MAX == UCHAR_MAX
inline bool lexicographical_compare(
  const char *_First1, const char *_Last1,
  const char *_First2, const char *_Last2)
{       // order [_First1, _Last1) vs. [First2, Last2), for nonnegative char
  ptrdiff_t _Num1 = _Last1 - _First1;
  ptrdiff_t _Num2 = _Last2 - _First2;
  int _Ans = _CSTD memcmp(_First1, _First2, _Num1 < _Num2 ? _Num1 : _Num2);
  return (_Ans < 0 || _Ans == 0 && _Num1 < _Num2); 
}
#endif

// TEMPLATE FUNCTION lexicographical_compare WITH PRED
template<class _InIt1,
  class _InIt2,
  class _Pr> inline
bool lexicographical_compare(_InIt1 _First1, _InIt1 _Last1,
                             _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
{       // order [_First1, _Last1) vs. [First2, Last2) using _Pred
  for (; _First1 != _Last1 && _First2 != _Last2; ++_First1, ++_First2)
    if (_Pred(*_First1, *_First2))
      return (true);
    else if (_Pred(*_First2, *_First1))
      return (false);
  return (_First1 == _Last1 && _First2 != _Last2); 
}

#ifndef _cpp_max
  #define _cpp_max  max /* retained */
  #define _cpp_min  min /* retained */
#endif
#ifndef _MAX   /* avoid collision with common (nonconforming) macros */
  #define _MAX  (max)
  #define _MIN  (min)
#endif

// TEMPLATE FUNCTION max
template<class _Ty> inline
const _Ty& _MAX(const _Ty& _Left, const _Ty& _Right)
{       // return larger of _Left and _Right
  return (_Left < _Right ? _Right : _Left); 
}

// TEMPLATE FUNCTION max WITH PRED
template<class _Ty,
  class _Pr> inline
const _Ty& _MAX(const _Ty& _Left, const _Ty& _Right, _Pr _Pred)
{       // return larger of _Left and _Right using _Pred
  return (_Pred(_Left, _Right) ? _Right : _Left); 
}

// TEMPLATE FUNCTION min
template<class _Ty> inline
const _Ty& _MIN(const _Ty& _Left, const _Ty& _Right)
{       // return smaller of _Left and _Right
  return (_Right < _Left ? _Right : _Left); 
}

// TEMPLATE FUNCTION min WITH PRED
template<class _Ty,
  class _Pr> inline
const _Ty& _MIN(const _Ty& _Left, const _Ty& _Right, _Pr _Pred)
{       // return smaller of _Left and _Right using _Pred
  return (_Pred(_Right, _Left) ? _Right : _Left); 
}

_STD_END
#endif /* _XUTILITY_ */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 V5.04:0576 */
